/**
 * @file 019.最多删除一个字符得到回文.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-19
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    // 给定一个非空串s，至多删除一个字符，能否得到回文串
    bool validPalindrome(string s)
    {
        // 双指针回文判断，若有不匹配 尝试++i或是--j,具体如何不知道
        int n = s.length();
        int i = 0, j = n - 1;
        while (i < j) {
            if (s[i] == s[j]) {
                ++i, --j;
            } else {
                return isValid(s, i + 1, j) || isValid(s, i, j - 1);
            }
        }
        return true;
    }
    bool isValid(string &s, int i, int j)
    {
        while (i < j) {
            if (s[i++] != s[j--]) {
                return false;
            }
        }
        return true;
    }
};

int main()
{
    std::cout << Solution().validPalindrome("aba") << std::endl;                   //1
    std::cout << Solution().validPalindrome("ebcbbececabbacecbbcbe") << std::endl; //1
    std::cout << Solution().validPalindrome("aguokepatgbnvfqmgmlcupu"
                                            "ufxoohdfpgjdmysgvhmvffc"
                                            "nqxjjxqncffvmhvgsymdjgp"
                                            "fdhooxfuupuculmgmqfvnbg"
                                            "tapekouga")
              << std::endl; //1
    return 0;
}